package graph;

import java.util.*;

/**
 * @ClassName aa
 * @Description TODO
 * @Author ZJX
 * @Date 2024/10/26 20:24
 * @Version 1.0
 */
public class LC207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
//        使用邻接表建图
        int[] inDegree = new int[numCourses];
        Map<Integer, List<Integer>> edges = new HashMap<>(); // 邻接表

        // 初始化邻接表
        for (int i = 0; i < numCourses; i++) {
            edges.put(i, new ArrayList<>());
        }

        // 构建图并计算入度
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int pre = prerequisite[1];
            edges.get(pre).add(course); // 在邻接表中添加边
            inDegree[course]++; // 目标课程入度加一
        }

        // 将所有入度为0的课程加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 拓扑排序处理
        int count = 0; // 记录已访问的节点数
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++; // 每完成一门课程，计数加一

            // 遍历该课程的所有后续课程
            for (int nextCourse : edges.get(course)) {
                inDegree[nextCourse]--; // 减少后续课程的入度
                if (inDegree[nextCourse] == 0) {
                    queue.offer(nextCourse); // 入度为0的课程加入队列
                }
            }
        }

        // 如果拓扑排序后访问的节点数等于课程总数，则可以完成所有课程
        return count == numCourses;
    }

}
